package com.leetcode.partition4;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/10/26 19:25
 */
public class LC399除法求值 {

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationsSize = equations.size();
        //极端情况下，每个分子和分母都不同，最多会出现 equationsSize * 2个不同的元素
        UnionFind unionFind = new UnionFind(equationsSize << 1);
        Map<String, Integer> hashMap = new HashMap<>(equationsSize << 1);
        int id = 0;
        for (int i = 0; i < equationsSize; i++) {
            List<String> equation = equations.get(i);
            //得到分子和分母，并将分子并入分母中，之间的结果为其带权路径
            String numerator = equation.get(0), denominator = equation.get(1);
            if (!hashMap.containsKey(numerator)) {
                hashMap.put(numerator, id++);
            }
            if (!hashMap.containsKey(denominator)) {
                hashMap.put(denominator, id++);
            }
            unionFind.union(hashMap.get(numerator), hashMap.get(denominator), values[i]);
        }
        double[] answers = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            Integer numeratorId = hashMap.get(queries.get(i).get(0));
            Integer denominatorId = hashMap.get(queries.get(i).get(1));
            if (numeratorId == null || denominatorId == null) answers[i] = -1.0d;
            else answers[i] = unionFind.isConnected(numeratorId, denominatorId);
        }
        return answers;
    }

    private static class UnionFind {

        private final int[] ancestor;
        //指向父节点的权值
        private final double[] weight;

        public UnionFind(int size) {
            ancestor = new int[size];
            weight = new double[size];
            for (int i = 0; i < size; i++) {
                ancestor[i] = i;
                weight[i] = 1.0d;
            }
        }

        public int find(int x) {
            if (ancestor[x] != x) {
                int origin = ancestor[x];
                ancestor[x] = find(ancestor[x]);
                //路径压缩，其权值也需要改变
                weight[x] *= weight[origin];
            }
            return ancestor[x];
        }

        public void union(int x, int y, double value) {
            int ancestorX = find(x), ancestorY = find(y);
            if (ancestorX != ancestorY) {
                ancestor[ancestorX] = ancestorY;
                //weight[x]*weight[ancestorX]==value*weight[y]，所以weight[ancestorX]=weight[y]*value/weight[x]
                weight[ancestorX] = weight[y] * value / weight[x];
            }
        }

        public double isConnected(Integer numeratorId, Integer denominatorId) {
            int ancestorX = find(numeratorId), ancestorY = find(denominatorId);
            if (ancestorX == ancestorY) return weight[numeratorId] / weight[denominatorId];
            return -1.0d;
        }
    }
}
